| 翻訳と辞書 |
| Certificate (complexity) ： ウィキペディア英語版 |
Certificate (complexity)
In computational complexity theory, a certificate (also called a witness) is a string that certifies the answer to a computation, or certifies the membership of some string in a language. A certificate is often thought of as a solution path within a verification process, which is used to check whether a problem gives the answer "Yes" or "No".
In the decision tree model of computation, certificate complexity is the minimum number of the input variables of a decision tree that need to be assigned a value in order to definitely establish the value of the Boolean function .
== Definition ==
Certificate is generally used to prove semi-decidability as following:
L ∈ SD iff there is a two-place predicate R ⊆ Σ∗ × Σ∗ such that R is computable, and such that for all x ∈ Σ∗:
x ∈ L ⇔ there exists y such that R(x, y)
and to prove NP as following:
L ∈ NP iff there is a polytime verifier V such that:
x ∈ L ⇔ there exists y such that |y| <= |x|c and V accepts (x, y)
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Certificate (complexity)」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|